package th.retrofit.lib;

import java.util.LinkedList;
import java.util.List;

/**
 * 给出集合[1,2,3,...,n]，其所有元素共有n! 种排列。
 *
 * 按大小顺序列出所有排列情况，并一一标记，当n = 3 时, 所有排列如下：
 *
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定n 和k，返回第k个排列。
 */
public class Solution60 {

    public String getPermutation(int n, int k) {
        List<Integer> data = new LinkedList<>();
        int[] arr = new int[n + 1];
        arr[0] = 1;
        for (int i = 1; i <= n; i++) {
            data.add(i);
            arr[i] = i * arr[i - 1];
        }
        StringBuilder sb = new StringBuilder();
        getPermutation(data, arr, sb, k - 1);
        return sb.toString();
    }

    private void getPermutation(List<Integer> data, int[] arr, StringBuilder sb, int k) {
        int size = data.size();
        if (k == 0) {
            for (int i = 0; i < size; i++) {
                sb.append(data.get(i));
            }
            return;
        }
        // 对(n - 1)!取余
        int value = k / arr[size - 1];
        sb.append(data.get(value));
        data.remove(value);
        getPermutation(data, arr, sb, k % arr[size - 1]);
    }

    public static void main(String[] args) {
        System.out.println(new Solution60().getPermutation(4, 9));
    }

}
